package com.cuz.hot100;

public class Q33searchRotatedSortedArray {
    public static void main(String[] args) {

       class A{
            public void nextPermutation(int[] nums) {

                if(nums == null || nums.length==0){
                    return ;
                }

                //找到从后向前不是升序的数
                int index = nums.length -2;
                //1 4 6 5 3 2,2 1
                while(index >= 0 && nums[index]>=nums[index+1]){
                    index--;
                }
                if(index>=0){
                    //找到第一个 大于num[index];
                    int swapIndex= nums.length-1;
                    while(swapIndex>=0&& nums[swapIndex]<=nums[index]){
                        swapIndex--;
                    }
                    swap(nums,swapIndex,index);
                }
                int start = index+1;
                int end = nums.length-1;
                while(start<end){
                    swap(nums,start,end);
                    start--;
                    end++;
                }
            }
            private void swap(int[]nums,int swapIndex,int index){
                int temp = nums[index];
                nums[index] = nums[swapIndex];
                nums[swapIndex] = temp;
            }
        }
        int[] ints = {3,2,1};
        new A().nextPermutation(ints);
        System.out.println(search1(ints, 1));
    }


    public static int search1(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        return findProcess(nums, 0, nums.length - 1, target);
    }

    private static int findProcess(int[] nums, int start, int end, int target) {
        while (start <= end) {
            int mid = ((end - start) >> 1) + start;
            int startValue = nums[start];
            int endValue = nums[end];
            int midValue = nums[mid];
            if (midValue == target) {
                return mid;
            }
            if (startValue == target) {
                return start;
            }
            if (endValue == target) {
                return end;
            }
            //4, 5, 6, 7, 8, 9, 10, 0, 1, 2
            //mid=8 找7
            //左边有序 且位于左边找左边
            //7 8 9 1 2 3  4 mid =1 start=7 右边有序
            //7 8 9 10 11 1 2 3  mid=10 start=7  左边有序
            if (midValue > startValue) {
                //左边搜索
                if (target < midValue && target > startValue) {
                    end = mid - 1;
                    start += 1;
                } else {
                    //右边搜索
                    end -= 1;
                    start = mid + 1;
                }
            } else {
                if (target > midValue && target < endValue) {
                    start = mid + 1;
                    end -= 1;
                } else {
                    start += 1;
                    end = mid - 1;
                }
            }

        }
        return -1;
    }
}
